Data Structure

In [1]:

    

# Node of a Singly Linked List
class Node:
    # constructor
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next
    
    # method of getter, setter for data
    def setData(self, data):
        self.data = data
    def getData(self):
        return self.data
    
    # method of getter, setter for next
    def setNext(self, next):
        self.next = next
    def getNext(self):
        return self.next
    
    # returns true if the node points to another node
    def hasNext(self):
        return self.next != None
        
# implement Singly Linked List
class SinglyLinkedList:
    def __init__(self, node=None):
        self.head = node
    
    def setHead(self, node):
        self.head = node
    def getHead(self):
        return self.head
    # returns length of list
    ## Time Complexity: O(n), for scanning the list of size n.
    ## Space COmplexity: O(1), for creating a temporary vaiable.
    def listLength(self):
        current = self.head
        count = 0
        
        while current != None:
            count += 1
            current = current.getNext()
            
        return count
    
    # method to insert
    ## - at beginning
    ## - at ending
    ## - at specific position
    def insertAtBeg(self, data):
        newNode = Node(data)
        length = self.listLength()
        
        if length == 0:
            self.setHead(newNode)
        else :
            newNode.setNext(self.getHead())
            self.setHead(newNode)
        
        return self
    
    def insertAtEnd(self, data):
        newNode = Node(data)
        current = self.getHead()
        
        while current.getNext() != None:
            current = current.getNext()
        
        current.setNext(newNode)
        return self

    def insertAtPos(self, data, pos):
        length = self.listLength()
        if pos > length or pos < 0:
            return None
        else:
            if pos == 0:
                self.insertAtBeg(data)
            else:
                newNode = Node(data)
                count = 0
                current = self.getHead()
                while count < pos - 1:
                    current = current.getNext()
                    count += 1
                newNode.setNext(current.getNext())
                current.setNext(newNode)
                return self
        
    # method to delete
    ## - at beginning
    ## - at ending
    ## - at specific position
    def deleteAtBeg(self):
        length = self.listLength()
        if length == 0:
            return None
        else :
            self.setHead(self.getHead().getNext())
            return self
    def deleteAtEnd(self):
        length = self.listLength()
        if length == 0:
            return None
        else :
            current = self.getHead()
            while current.getNext() != None:
                prev = current
                current = current.getNext()
            prev.setNext(None)
            return self
    def deleteAtPos(self, pos):
        length = self.listLength()
        if pos > length or pos < 0:
            return None
        else:
            count = 0
            current = self.getHead()
            while count < pos - 1:
                count += 1
                current = current.getNext()
            current.setNext(current.getNext().getNext())
            return self
        
    def show(self):
        current = self.getHead()
        acc = str(current.getData())
        while current.getNext() != None:
            current = current.getNext()
            acc = acc + "::" + str(current.getData())
        return acc+"::Null"


    

In [2]:

    

ls = SinglyLinkedList(Node(1))
print(ls.insertAtBeg(3).show())
print(ls.insertAtBeg(5).show())
print(ls.insertAtEnd(8).show())
print(ls.insertAtPos(12, 2).show())
print(ls.deleteAtPos(3).show())
print(ls.deleteAtEnd().show())
print(ls.deleteAtBeg().show())


    

    




3::1::Null
5::3::1::Null
5::3::1::8::Null
5::3::12::1::8::Null
5::3::12::8::Null
5::3::12::Null
3::12::Null

In [3]:

    

# Node of a Doubly Linked List
class Node:
    def __init__(self, data=None, next=None, prev=None):
        self.data = data
        self.next = next
        self.prev = prev
  
    def setNext(self, next):
        self.next = next
    def getNext(self):
        return self.next

    def setPrev(self, prev):
        self.prev = prev
    def getPrev(self):
        return self.prev

    def setData(self, data):
        self.data = data
    def getData(self):
        return self.data

# It is recommended to implement a doubly linked list 
# by referring to the above singly linked list implementation.

class DoublyLinkedList():
    pass